1485. Серия степеней матриц

 

По заданной матрице A размера n×n и положительному целому значению k вычислить сумму S = A + A2 + A3 + … + Ak.

 

Вход. Первая строка содержит три положительных целых числа n (n ≤ 30), k (k ≤ 109) и m (m < 104). Каждая из следующих n строк содержит n неотрицательных целых чисел меньших 32768, задающих элементы матрицы A в порядке возрастания строк.

 

Выход. Вывести элементы матрицы S по модулю m в таком же виде как и входная матрица A.

 

Пример входа

Пример выхода

2 2 4

0 1

1 1

1 2

2 3

 

 

РЕШЕНИЕ

алгебра

 

Анализ алгоритма

Пусть Sk = A + A2 + … + Ak.

Если k четное, то

Sk = A + A2 + … + Ak = A + A2 + … + Ak/2 + Ak/2+1 +  … + Ak =

= (A + A2 + … + Ak/2) + Ak/2 * (A + A2 + … + Ak/2) =

= Sk/2 + Sk/2 * Ak/2

Если k нечетное, то

Sk = A + A2 + … + Ak =

(A + A2 + … + Ak – 1) * A + A = Sk-1 * A + A

 

Реализация алгоритма

Реализуем класс матрица. Переопределим операции сложения, умножения и возведения в степень.

 

#pragma comment(linker, "/STACK:100000000")

#define MAX 32

 

class Matrix

{

public:

  int n;

  long long m[MAX][MAX];

  Matrix(int size = 0, int value = 0)

  {

    n = size;

    memset(m,0,sizeof(m));

    for(int i = 0; i < n; i++)

      m[i][i] = value;

  }

 

  Matrix operator +(Matrix &a) const

  {

    Matrix res(a.n,0);

    for (int i = 0; i < n; i++)

      for (int j = 0; j < n; j++)

        res.m[i][j] = (m[i][j] + a.m[i][j]) % mod;

    return res;

  }

 

  Matrix operator *(Matrix &a) const

  {

    Matrix res(a.n,0);

    for(int i = 0; i < n; i++)

    for(int j = 0; j < n; j++)

    {

      long long s = 0;

      for(int k = 0; k < n; k++)

        s = (s + m[i][k] * a.m[k][j]) % mod;

      res.m[i][j] = s;

    }

    return res;

  }

 

  Matrix operator^ (int n)

  {

    Matrix x(*this);

    if (n == 1) return x;

    if (n & 1) return x * ((x * x) ^ (n/2));

    return (x * x) ^ (n/2);

  }

 

  void Print(void)

  {

    for(int i = 0; i < n; i++)

    {

      for(int j = 0; j < n - 1; j++)

        printf("%d ",m[i][j]);

      printf("%d\n",m[i][n-1]);

    }

  }

};

 

Вычисление суммы Sk = A + A2 + … + Ak.

 

Matrix sum(Matrix a, int k)

{

  if (k == 1) return a;

  if (k % 2)

  {

    Matrix b = sum(a,k-1);

    return b * a + a;

  }

  Matrix b = sum(a,k/2);

  return b + b * (a ^ (k/2));

}

 

Основная часть программы. Читаем входные данные.

 

Matrix a, res;

scanf("%d %d %d",&n,&k,&mod);

 

a.n = n;

for(i = 0; i < n; i++)

  for(j = 0; j < n; j++)

  {

    scanf("%d",&a.m[i][j]);

    a.m[i][j] %= mod;

  }

 

Вычисляем и выводим ответ.

 

res = sum(a,k);

res.Print();